package dfsketches.bicycles;

public class SparseVoxelOctotree implements Structure3d {

	public class Octonode {
		int data;
		Octonode[] child;
		public Octonode(int data) {
			this.data = data;
		}
		public void split() {
			child = new Octonode[8];
		}
		public int getChildN() {
			int n = 1;
			if (child != null)
				for (int i = 0; i < 8; i++)
					n += (child[i] != null) ? child[i].getChildN() : 0;
			return n;
		}
	}
	
	Octonode root;
	int sz;
	
	public SparseVoxelOctotree(int size) {
		this(size, 0);
	}
	
	public SparseVoxelOctotree(int size, int initVal) {
		root = new Octonode(initVal);
		sz = size - 1;
	}
	
	public void put(int x, int y, int z, int data) {
		put(x,y,z,x,y,z, data);
	}
	
	public void put(
			int x1, int y1, int z1,
			int x2, int y2, int z2,
			int data) {
		put(x1,y1,z1, x2,y2,z2, data, 0,0,0, sz,sz,sz, root, null, -1);
	}
	
	private void put(
			int x1, int y1, int z1,
			int x2, int y2, int z2, int data,
			int xs, int ys, int zs,
			int xf, int yf, int zf, Octonode node, Octonode parent, int idx) {
		if (in(xs,ys,zs, x1,y1,z1, x2,y2,z2) && in(xf,yf,zf, x1,y1,z1, x2,y2,z2)) {
			if (node == null) {
				parent.child[idx] = node = new Octonode(data);
			} else {
				node.data = data;
				node.child = null;
			}
		} else if (x1 < xs && x2 < xs || y1 < ys && y2 < ys || z1 < zs && z2 < zs
				|| x1 > xf && x2 > xf || y1 > yf && y2 > yf || z1 > zf && z2 > zf) {
			//do nothing
		} else {
			if (node == null) {
				parent.child[idx] = node = new Octonode(parent.data);
			}
			if (node.child == null) node.split();
			int xm = (xs + xf) >> 1;
			int ym = (ys + yf) >> 1;
			int zm = (zs + zf) >> 1;
			put(x1,y1,z1, x2,y2,z2, data, xs,  ys,  zs,   xm,ym,zm, node.child[0], node, 0);
			put(x1,y1,z1, x2,y2,z2, data, xm+1,ys,  zs,   xf,ym,zm, node.child[1], node, 1);
			put(x1,y1,z1, x2,y2,z2, data, xs,  ym+1,zs,   xm,yf,zm, node.child[2], node, 2);
			put(x1,y1,z1, x2,y2,z2, data, xm+1,ym+1,zs,   xf,yf,zm, node.child[3], node, 3);
			put(x1,y1,z1, x2,y2,z2, data, xs  ,ys,  zm+1, xm,ym,zf, node.child[4], node, 4);
			put(x1,y1,z1, x2,y2,z2, data, xm+1,ys,  zm+1, xf,ym,zf, node.child[5], node, 5);
			put(x1,y1,z1, x2,y2,z2, data, xs  ,ym+1,zm+1, xm,yf,zf, node.child[6], node, 6);
			put(x1,y1,z1, x2,y2,z2, data, xm+1,ym+1,zm+1, xf,yf,zf, node.child[7], node, 7);
			
			int d = node.data;
			boolean d_not_init = true;
			boolean has_null_child = false;
			boolean all_solid = true;
			boolean data_equal = true;
			for (Octonode n : node.child) {
				if (n != null) {
					if (d_not_init) {
						d = n.data;
						d_not_init = false;
					} else {
						if (d != n.data) {
							data_equal = false;
						}
					}
					if (n.child != null) {
						all_solid = false;
					}

				} else {
					has_null_child = true;
				}
			}
			if (all_solid && data_equal && d == node.data) {
				node.child = null;
			}
			if (all_solid && data_equal && !has_null_child) {
				node.child = null;
				node.data = d;
			}
		}
	}
	
	private boolean in(int x, int y, int z,
			int x1, int y1, int z1,
			int x2, int y2, int z2) {
		return (x1 <= x && x <= x2 &&
				y1 <= y && y <= y2 &&
				z1 <= z && z <= z2);
	}
	
	public int get(int x, int y, int z) {
		int xs = 0;
		int ys = 0;
		int zs = 0;
		int xf = sz;
		int yf = sz;
		int zf = sz;
		Octonode node = root;
		Octonode parent = root;
		while (xf - xs > 0 && node != null && node.child != null) {
			int xm = (xs + xf) >> 1;
			int ym = (ys + yf) >> 1;
			int zm = (zs + zf) >> 1;
			int childN = 0;
			if (x > xm) {childN += 1; xs = xm+1;} else xf = xm;
			if (y > ym) {childN += 2; ys = ym+1;} else yf = ym;
			if (z > zm) {childN += 4; zs = zm+1;} else zf = zm;
			parent = node;
			node = node.child[childN];
		}
		return (node != null) ? node.data : parent.data;
	}

	public int getChildN() {
		return root.getChildN();
	}

	@Override
	public void put(int x, int y, int z_from, int z_to, int value) {
		for (int z = z_from; z < z_to; z++)
			put(x, y, z, value);
	}

	@Override
	public int getWidth() {
		return sz;
	}

	@Override
	public int getHeight() {
		return sz;
	}
	
}
